Three-dimensional digital representations of objects are commonly used in the fields of engineering, medical science, video games, cinema, and even in mass market applications (for example Sketch Up by Google, now Trimble). This practice is made possible by 3D creation and editing software, including CAD (Computer-aided design) systems, reverse engineering and other 3D reconstruction techniques, but also thanks to 3D scanners. All these methods generate digital models in 3 dimensions. Some create 3D models describing limits between objects and their environment, and are known as boundary representation or B-rep, seen for example in the STEP standard or in geometric modelling kernels like Parasolid or Acis. Others go with a tessellation (STL or VRML formats, for example). Those models can include more information, which is not strictly geometric.
The aforementioned 3D model types are commonly used in businesses and in multiple aspects of day to day life, and their popularity are rapidly increasing. As a result, several problems exist relating to: (i) indexing 3D models; (ii) retrieving similar digital objects; (iii) comparing them in order to identify their differences or identical parts; and (iv) displaying relevant results to insure an exploitation which is simple and efficient according to the defined criteria.
There are currently two distinct categories of systems: the first category relates to comparing a reference 3D model with a second 3D model and determine the differences between them, whereas the second category relates to searching for 3D models which resemble a reference 3D model.
Systems/Tools for Comparing 3D Models
Several computer applications, such asked systems, offer methods to precisely compare two 3D models with one another, or to compare a 3D model with a scatter plot or a 3D model created from a real object. In such methods, two 3D models are first selected. Multiple methods can then be used to compare these two models. It is possible to compare topological and geometrical structures using a graphing approach (Graph mapping, for example as described in WO 2007/098929 A1), or using a point-based method (for example, as described in U.S. Pat. No. 7,149,677 B2, or by using the method of least squares as used in Innovmetric's product or U.S. Pat. No. 8,072,450 B2). Some methods require that both models use the same frame of reference, be on the same computer application (same CAD system, for example), and use the same geometric representation. Geometric and topological-based methods imperatively require that both the 3D models being compared respect these conditions. Depending on the comparison method used, the 3D models can be marked to distinguish identical parts and different parts of the two 3D models by associating for example a state (identical, modified, unique) or quantifying the differences between them (a distance between points in models A and B respectively, for example). The results of the comparison are then displayed, either by (i) superimposing the two 3D models; (ii) applying a color gradient to highlight the differences between models A and B or vector fields; or (iii) by applying a colour code in accordance with the state defined in the previous module. This comparison indicates the parts of the 3D model (or the faces) that are identical, the unique parts (non-matched faces) or modified (matched faces with a difference), and possibly parts added on one model but not the other (through asymmetric display which shows what exists on A with respect to B, and what exists on B with respect to A). Even though all these systems are different, they have one common point: when comparing the reference 3D model with the target 3D model, they pick a single frame of reference or a unique “best fit” from which they will compare the complete 3D models to show the differences.
The Geometric Ltd application included in SolidWorks is a typical example of this category.
Systems/Tools for Searching 3D Models
A second category of computer applications offers the ability to search for 3D models by comparing a reference 3D model with a set of 3D models, with the goal of selecting 3D models based on their resemblance with the reference 3D model. This resemblance is usually expressed by a quantitative value used to rank the 3D models. Multiple methods are available to determine this resemblance. First, each 3D model is analysed in view of producing a more efficient representation to later perform the comparisons. This representation is often labelled under multiple terms, such as a descriptor, a representation, and an index. Notwithstanding its appellation, this representation can have multiple forms, for example a graph (US 2004/0249809 A1), a fixed vector of N dimensions (U.S. Pat. No. 6,625,607 B1) or a vector varying according to the 3D model, etc. These descriptors are usually saved for use when the comparisons are performed. A 3D model is picked to be used as a reference. In some cases, the reference 3D model is replaced by images, photos or drawings in 2 dimensions [A 3D Model Search Engine, Patrick Min, Ph.D. Dissertation, Princeton University, 2004]. If necessary, its descriptor is calculated. The descriptors are compared. Here too, multiple methods are described in [Content-based Three-dimensional Engineering Shape Search, K. Lou, S. Prabhakar, K. Ramani, Proceedings of the 20th International Conference on Data Engineering 2004]. According to the results of the comparison, the similar 3D models are generally ranked by a quantity, which is called a similarity or resemblance index. These results are then displayed in different forms, usually using small-sized images (icons, thumbnails).
As mentioned previously, numerous approaches have been proposed to search 3D models using a reference 3D model. Some approaches look for organic shapes, while others look for permissive similarities (e.g. locating cars, chairs, glasses). These methods were not conceived to determine whether two 3D models are exactly the same, with a precision of the same order of magnitude as their manufacturing tolerance. Systems like Geolus by Siemens or GeoSearch by Cadenas are representative of this category. They analyze 3D models approximated by flat-representations to generate their descriptors, which inevitably deteriorates their precision. Known methods which extract descriptors from 3D models and compare them with each other typically demand a lengthy computation time and are thus difficult to apply when there is an significant number of 3D models to process (more than a million, for example), or for an interactive search.
However, known search systems or tools for 3D models do not have the information nor the technology to offer the possibility to launch a search based on complete 3D models that favour certain parts of those models.